// m

// 给定一个循环数组nums（最后一个元素的下一个元素是数组的第一个元素）
// 要求：输出每个元素的下一个更大元素，如果不存在，则输出-1 

// 思路1： 暴力求解，对于nums中的每一个元素nums[i],查找nums[i]右边第一个比nums[i]大的元素，这种解法的时间复杂度是O(n^2)
// 思路2：使用单调递增栈，遍历数组nums，构造单调递增栈，求出nums每个元素右侧下一个更大的元素，然后将其存储到答案数组中，这种解法的时间复杂度是O(n)
// 而循环数组的求解方法可以将nums复制一份到末尾，生成长度为2 * len(nums)的数组，或者通过取模运算将下标映射到0~len(nums) * 2 - 1之间

function nextGreaterElements(nums) {
    let size = nums.length
    let res = new Array(size).fill(-1)
    let stack = []
    for (let i = 0; i < 2 * size; i++) {
        while (stack.length && (nums[i % size] > nums[stack[stack.length - 1]])) {
            let index = stack.pop()
            res[index] = nums[i % size]
        } 
        stack.push(i % size)       
    }
    return res
};

let nums = [1,2,2,3,4,3]
console.log(nextGreaterElements(nums))